#
# @lc app=leetcode.cn id=28 lang=python
#
# [28] 实现 strStr()
#
# @lc code=start
class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        # 子串逐一比较
        haystack_length = len(haystack)
        needle_length = len(needle)
        for start in range(haystack_length - needle_length + 1):
            if haystack[start: start+needle_length] == needle:
                return start
        return -1


class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        # 双指针的方法实现
        i, j = 0, 0
        cur_len = 0     # 已匹配长度
        haystack_length = len(haystack)
        needle_length = len(needle)
        # 为空的情况
        if needle_length == 0:
            return 0
        # 正常情况
        while i < haystack_length and j < needle_length:
            if haystack[i] == needle[j]:
                if j == needle_length - 1:
                    return i - needle_length + 1
                i += 1
                j += 1
                cur_len += 1
            else:
                i = i - cur_len + 1
                j = 0
                cur_len = 0
            
        return -1


class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        # Rabin Karp ———— 常熟复杂度
        haystack_length = len(haystack)
        needle_length = len(needle)

        # 判断needle比haystack长的情况
        if needle_length > haystack_length:
            return -1

        # 定义基base和模modulus
        base = 26
        modulus = 2**31

        # 定义字符转整形的哈希函数
        haystack_to_int = lambda i: ord(haystack[i]) - ord('a')
        needle_to_int = lambda i: ord(needle[i]) - ord('a')

        # 计算needle以及haystack在0的位置对应的转换哈希值
        h = h_ref = 0
        for i in range(needle_length):
            h = (h*base + haystack_to_int(i)) % modulus
            h_ref = (h_ref*base + needle_to_int(i)) % modulus

        if h == h_ref:
            return 0
        base_needle = pow(base, needle_length, modulus)
        for start in range(1, haystack_length - needle_length + 1):
            h = (h*base - haystack_to_int(start-1)*base_needle + haystack_to_int(start+needle_length-1)) % modulus
            if h == h_ref:
                return start

        return -1


# @lc code=end

if __name__ == "__main__":
    solution = Solution()
    print(solution.strStr('hello', 'll'))